package a_erfenchazhao;

/**
 * @ClassName E_LeftMostJiChuXieFa
 * @Description 遇到重复元素 找到最靠左的
 * @Author Zhang Li Tao
 * @Date 2024/3/17
 * @Version 1.0
 **/
public class E_LeftMostJiChuXieFa {
    public static void main(String[] args) {
        int[] array = {0, 1, 2, 3, 5, 5, 5, 5, 6, 7, 8};
        int target = 5;

        int leftIndex = 0;
        int rightIndex = array.length - 1;

        // 用于每次找到目标值的索引
        int resultIndex = -1;

        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < array[middleIndex]) { // 左半部分
                rightIndex = middleIndex - 1;
            } else if (array[middleIndex] < target) { // 右半部分
                leftIndex = middleIndex + 1;
            } else {
                // 即使找到也不会终止程序 会继续往左边找找看
                resultIndex = middleIndex; // 记录当前找到的索引
                rightIndex = middleIndex - 1; // 右边界左移到当前目标索引的左一位
            }
        }

        System.out.println(resultIndex);
    }
}
